/**
 * Created by sunchenglin on 2017/7/17.
 * //    堆排序
 
 */
public class Solution {

//  上浮，例如插入新的节点
    public static void swim(int i,int[]array, int N){
        while((i-1)/2>=0){
            if(array[i]>array[(i-1)/2]){
                change(i,(i-1)/2,array);
                i = (i-1)/2;
            }else{
                break;
            }
        }
    }
    public static void sink(int i,int[] array,int N){
//        如果比儿子小，从儿子中选较大的替换，降
//        换了的替换为i，继续sink
        int maxIndex;
        while(i<=N/2-1){
//            如果只有一个左儿子
            if(2*i+2>=N)
                maxIndex = 2*i+1;
            else
                maxIndex = (array[2*i+1]>array[2*i+2])? 2*i+1:2*i+2;
            if(array[i]<array[maxIndex]){
                change(i,maxIndex,array);
                i = maxIndex;
            }else{
                break;
            }
        }
    }

    public static void change(int i, int j, int[] array){
        int temp;
        temp = array[i];
        array[i] =array[j];
        array[j] = temp;
    }

    public static void sort(int[] array){
//        交换第一个和最后一个，sink，
        int N =array.length;
        for(int i=0;i<array.length;i++){
            change(0,--N,array);
            sink(0,array, N);
        }
    }

//最大堆构建
//下沉构建堆，N/2次下沉，如果使用swim，需要N次，每次插入都要swim
    public static void maxHeap(int[] array){

        for(int i=(array.length)/2-1;i>=0;i--)
            sink(i,array,array.length);
    }
    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        maxHeap(a);
        sort(a);
        System.out.println("haha");
    }
}
